Surrounded regions

Time: O(MxN); Space: O(M+N); medium

Given a 2D board containing ‘X’ and ‘O’, capture all regions surrounded by ‘X’.

A region is captured by flipping all ’O’s into ’X’s in that surrounded region.

Example 1:

Input: board =

X X X X
X O O X
X X O X
X O X X

Output: board =

X X X X
X X X X
X X X X
X O X X

import collections

class Solution:
    # Capture all regions by modifying the input board in-place.
    # Do not return any value.
    def solve(self, board):
        '''
        :type board: 2D array
        :rtype: None
        '''
        if not board:
            return
        q = collections.deque([])

        for i in range(len(board)):
            q.append((i, 0))
            q.append((i, len(board[0]) - 1))

        for j in range(len(board[0])):
            q.append((0, j))
            q.append((len(board) - 1, j))

        while q:
            i, j = q.popleft()
            if board[i][j] in ['O', 'V']:
                board[i][j] = 'V'
                for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
                    if 0 <= x < len(board) and 0 <= y < len(board[0]) and \
                       board[x][y] == 'O':
                        board[x][y] = 'V'
                        q.append((x, y))

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] != 'V':
                    board[i][j] = 'X'
                else:
                    board[i][j] = 'O'

if __name__ == "__main__":
    board = [['X', 'X', 'X', 'X'],
             ['X', 'O', 'O', 'X'],
             ['X', 'X', 'O', 'X'],
             ['X', 'O', 'X', 'X']]
    Solution().solve(board)
    assert board == [['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'X']]

See also:

https://leetcode.com/problems/surrounded-regions

https://www.lintcode.com/problem/surrounded-regions